ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpa/doc/main.tex

   1 \documentclass[10pt,a4paper,notitlepage]{article}
   2 \usepackage[spanish]{babel}
   3 \usepackage{amsmath,amssymb}
   4 \usepackage{algorithmic}
   5
   6 \begin{document}
   7
   8 \section{100 - The $3n + 1$ problem}
   9
  10 \section{861 - Little bishops}
  11
  12 \section{10020 - Minimal coverage}
  13
  14 Problema: dado un conjunto de intervalos $[L_i,R_i)$, determinar
  15 un subconjunto que cubra el segmento $[0,M)$ y que sea m\'inimo
  16 (en el sentido de cardinalidad). En el enunciado los intervalos
  17 se notan $[L,R]$, pero como los extremos son enteros y hay que
  18 cubrir intervalos reales, los problemas son equivalentes.
  19
  20 Se resolvi\'o mediante una t\'ecnica golosa. La idea del algoritmo
  21 es tomar en cada paso alguno de los intervalos cuyo borde izquierdo
  22 ya se encuentre cubierto (o a lo sumo coincida con el punto m\'as chico
  23 que todav\'ia no est\'e cubierto) y cuyo borde derecho sea lo mayor posible.
  24
  25 \vspace{10pt}
  26 \begin{algorithmic}
  27 \STATE Entrada: $A$: conjunto de intervalos $[L,R)$.
  28 \STATE Salida: $S$: un conjunto m\'inimo de intervalos de $A$ que cubren $[0,M)$.
  29 \STATE $A^\star :=$ intervalos no vac\'ios de $A$ ordenados crecientemente por $L$.
  30 \STATE $final := 0$
  31 \STATE $S := [\,]$
  32 \WHILE {$final < M$}
  33   \IF {$A^\star$ es vac\'ia $\lor$ \big($A^\star_0 = [L,R)$ con $L > final$\big)}
  34     \STATE --- No se puede cubrir el intervalo $[0,M)$ ---
  35     \STATE Fallar.
  36   \ELSE
  37     \STATE $C := \{ [L,R) \gets A^\star \text{ tales que } L \leq final \}$
  38     \STATE --- $C$ corresponde a un prefijo no vac\'io de $A^\star$ ---
  39     \STATE $I := [L_I,R_I) \in C$ tal que $R_I = \max\{R : [L,R) \in C\}$
  40     \IF {$R_I \leq final$}
  41       \STATE --- No se puede cubrir el intervalo $[0,M)$ ---
  42       \STATE Fallar.
  43     \ENDIF
  44     \STATE Agregar $I$ a $S$.
  45     \STATE $A^\star := $ sufijo de $A^\star$ omitiendo los primeros $\#C$ elementos
  46     \STATE $final := R_I$
  47   \ENDIF
  48 \ENDWHILE
  49 \end{algorithmic}
  50 \vspace{10pt}
  51
  52 El algoritmo termina porque en la rama del {\bf else}
  53 el conjunto $C$ nunca es vac\'io, y por lo tanto $A^\star$
  54 se va achicando.
  55
  56 El invariante del algoritmo es que los intervalos en $S$ cubren el
  57 intervalo $[0,final)$.
  58 Al entrar en una iteraci\'on, todav\'ia falta cubrir el intervalo
  59 $[final, M)$. En la rama del {\bf then}, no se puede cubrir
  60 $[final, M)$ y por lo tanto tampoco $[0,M)$.
  61
  62 En la rama del {\bf else}, es claro que el conjunto $C$ no es vac\'io.
  63 Corresponde a un prefijo de $A^\star$ porque los elementos de $A^\star$
  64 est\'an ordenados. Si hay soluci\'on, al menos un intervalo de $C$ debe
  65 figurar en ella, porque todos los intervalos restantes de $A^\star$ no
  66 cubren el punto $final$. Se puede encontrar una soluci\'on m\'inima
  67 tomando $I$ como alguno de los intervalos de $C$ cuyo extremo
  68 derecho sea mayor.
  69 Al incluir $I$ en la soluci\'on, todos los dem\'as intervalos
  70 de $C$ quedan cubiertos por el contenido de $S$ y por lo tanto
  71 se pueden excluir de $A^\star$.
  72
  73 Adem\'as, incluir $I$ en la soluci\'on no puede ser una mala
  74 decisi\'on (que ``moleste'' en iteraciones posteriores), porque
  75 el hecho de elegir un valor m\'as grande de $R_I$ hace que
  76 en iteraciones posteriores el valor de $final$ sea mayor y
  77 por lo tanto el conjunto $C$ incluya m\'as intervalos.
  78
  79 Para una entrada de $n$ intervalos, la complejidad del algoritmo
  80 es $O(n \log n)$ en peor caso. El paso m\'as costoso es ordenarlos.
  81 Es claro que el resto del algoritmo se reduce a
  82 hacer una pasada sobre los intervalos ya ordenados\footnote{
  83 Se podr\'ia mejorar la complejidad para que ordenarlos
  84 fuera $O(n)$ haciendo bucket sort. El enunciado afirma que el valor
  85 de los extremos $L_i, R_i$ es a lo sumo $50000$. Pueden ser negativos,
  86 pero para este problema ser\'ia equivalente considerar los
  87 intervalos $[\max(L_i,0),\max(R_i,0))$.
  88 }.
  89 Las operaciones para manipular intervalos son $O(1)$ porque
  90 los extremos se representan con enteros de 32 bits.
  91
  92 En la implementaci\'on del algoritmo en C++ no se incluye el {\bf if}
  93 cuya condici\'on es $R_I \leq final$. En ese caso, el
  94 algoritmo falla en la siguiente iteraci\'on, porque si
  95 $A^\star$ no es vac\'ia, el primer intervalo no puede ser
  96 tal que $L \leq final$.
  97
  98 \section{10069 - Distinct subsequences}
  99
 100 Problema: dadas dos strings $x = x_0 \hdots x_n$ y $z = z_0 \hdots z_m$,
 101 determinar la cantidad de ocurrencias distintas de $z$ como subsecuencia de $x$.
 102 (Dos ocurrencias son distintas si les corresponden distintas secuencias
 103 de \'indices).
 104
 105 Se resolvi\'o mediante un algoritmo de programaci\'on din\'amica.
 106 Se define la siguiente funci\'on $M(i,j)$ para $i \in [0,n]$, $j \in [0,m]$:
 107 $$M(i,j) = \text{cantidad de ocurrencias de $z[0..j)$ como subsecuencia de $x[0..i)$}$$
 108
 109 \noindent
 110 Definida concretamente por las siguientes ecuaciones:
 111
 112 \vspace{10pt}
 113 \begin{tabular}{ll}
 114 $M(i,0) = 1$ &\vspace{5pt}\\
 115 $M(0,j) = 0$ \text{ (para $j > 0$)}&\vspace{5pt}\\
 116 $M(i,j) = M(i - 1, j) + \begin{cases}
 117 M(i - 1, j - 1) & \text{ si $x_{i - 1}$ = $z_{j - 1}$ }\\
 118 0 & \text{ si no}
 119 \end{cases}$
 120 & (para $i, j > 0$)
 121 \end{tabular}
 122 \vspace{10pt}
 123
 124 La primera ecuaci\'on afirma que la cadena vac\'ia ocurre una vez en cualquier otra cadena
 125 (la secuencia de \'indices de la cadena vac\'ia es una secuencia vac\'ia).
 126 La segunda ecuaci\'on afirma que cualquier cadena no vac\'ia no ocurre en la cadena vac\'ia.
 127 En la tercera ecuaci\'on se afirma que:
 128 \begin{itemize}
 129 \item Todas las ocurrencias de $z[0..j)$ en $x[0..i-1)$
 130       son ocurrencias de $z[0..j)$ en $x[0..i)$.
 131 \item Adem\'as, si $x_{i - 1} = z_{j - 1}$, cada una de las ocurrencias de
 132       $z[0..j-1)$ en $x[0..i-1)$ tiene asociada una ocurrencia de
 133       $z[0..j)$ en $x[0..i)$.
 134 \item Es claro que no puede haber otras ocurrencias de $z[0..j)$ en $x[0..i)$
 135       y que los dos tipos de ocurrencias descriptos son disjuntos,
 136       de modo que alcanza con sumarlos.
 137 \end{itemize}
 138
 139 El algoritmo se implementa computando la matriz de la funci\'on $M$,
 140 visitando una vez cada posici\'on de la matriz. S\'olo se necesita el
 141 resultado, $M(n,m) = $ cantidad de ocurrencias de $z$ en $x$. Alcanza
 142 con mantener en memoria s\'olo las dos \'ultimas columnas de $M(i,j)$.
 143 La complejidad temporal es $O(n \cdot m)$ en peor caso.
 144
 145 \subsection{Aritm\'etica de n\'umeros grandes}
 146
 147 El enunciado afirma que $|x| \leq 10000$, $|z| \leq 100$ y que la cantidad de
 148 ocurrencias de $z$ en $x$ es a lo sumo $10^{100}$, que obviamente no cabe en registros
 149 de 64 bits. Adem\'as, la afirmaci\'on no es espuria porque {\em pueden} darse
 150 situaciones en las que el n\'umero de ocurrencias sea mucho mayor que $10^{100}$.
 151 Por ejemplo, tomando $x = a^{10000}$ y $z = a^{100}$, hay
 152 $10000 \choose 100$ ocurrencias de $z$ en $x$.
 153
 154 La \'unica operaci\'on requerida por el algoritmo es la suma de n\'umeros
 155 grandes. Se program\'o una clase \texttt{BigInt} que representa
 156 un n\'umero natural con un vector de 16 d\'igitos en base
 157 $10^8$. Esto permite representar enteros en $[0,10^{128})$
 158 e imprimir la salida en base 10 sin recurrir a divisiones.
 159
 160 La suma de n\'umeros grandes es $O(1)$ porque est\'an representados
 161 con un arreglo que siempre tiene exactamente 16 d\'igitos. La
 162 implementaci\'on de la suma con carry es la usual.
 163
 164 \end{document}
 165